﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace 马踏棋盘
{
    public class Solution
    {
        public static int row = 12;
        public static int col = 12;
        public static int[,] turn = new int[,] { { 1, 2 }, { 1, -2 }, { -1, 2 }, { -1, -2 }, { 2, 1 }, { 2, -1 }, { -2, 1 }, { -2, -1 } };
        public int[,] map;
        public int maxcount = 0;
        public bool success = false;

        public Solution(int maxrow, int maxcol)
        {
            row = maxrow + 4;
            col = maxcol + 4;
            map = new int[row, col];
            for (int i = 0; i < row; i++)
            {
                for (int j = 0; j < col; j++)
                {
                    if (i < 2 || i >= row - 2 || j < 2 || j >= col - 2)
                    {
                        map[i, j] = -1;
                    }
                    else
                    {
                        map[i, j] = 0;
                    }
                }
            }
            maxcount = (row - 4) * (col - 4);
        }

        public List<int> Steps(int i, int j)
        {
            List<int> steps = new();

            int x, y;

            for (int k = 0; k < turn.GetLength(0); k++)
            {
                x = i + turn[k, 0];
                y = j + turn[k, 1];
                if (map[x, y] == 0)
                {
                    steps.Add(k);
                }
            }

            return steps;
        }

        public void Print()
        {
            for (int i = 2; i < row - 2; i++)
            {
                for (int j = 2; j < col - 2; j++)
                {
                    Console.Write("{0:d2} ", map[i, j]);
                }
                Console.WriteLine();
            }
        }

        public void Dfs(int i, int j, int number)
        {
            map[i, j] = number;
            if (number >= maxcount)
            {
                success = true;
                return;
            }

            var steps = Steps(i, j);
            var nexts = new List<NextStep>();
            foreach (var step in steps)
            {
                var count = Steps(i + turn[step, 0], j + turn[step, 1]).Count;
                nexts.Add(new(step, count));
            }
            nexts.Sort();

            foreach (var next in nexts)
            {
                Dfs(i + turn[next.index, 0], j + turn[next.index, 1], number + 1);
                if (success)
                {
                    return;
                }
            }

            map[i, j] = 0;
        }
    }

    public struct NextStep : IComparable
    {
        public int count;
        public int index;

        public NextStep(int index, int count)
        {
            this.index = index;
            this.count = count;
        }

        public int CompareTo(object obj)
        {
            NextStep next = (NextStep)obj;
            return this.count - next.count;
        }
    }
}
